#include<bits/stdc++.h>
using namespace std;
vector<int>v[100];
vector<bool>visited(1001, false);
vector<int>arr;
void print()
{
    cout << "{ ";
    for (int i = 0; i < arr.size(); i++)
    {
        if (i)
          cout << " ";
        cout << arr[i];
    }
    cout << " }";
}
void dfs(int start)
{
    if (visited[start] == true)
    {
        return;
    }
    visited[start] = true;
    arr.push_back(start);
    for (int i = 0; i < v[start].size(); i++)
    {
        if(v[start].size() != 0)
        dfs(v[start][i]);
    }
}
void bfs(int start)
{
    deque<int>q;
    q.push_back(start);
    arr.push_back(start);
    visited[start] = true;
    while (q.size())
    {
        int head = q[0];
        q.pop_front();
        for (int i = 0; i < v[head].size(); i++)
        {
            if (!visited[v[head][i]])
            {
                arr.push_back(v[head][i]);           
                q.push_back(v[head][i]);
                visited[v[head][i]] = true;
            }
        }
    }
}
int main(void)
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for (int i = 0; i < m; i++)
    {
        sort(v[i].begin(),v[i].end());
    }
    for (int i = 0; i < n; i++)
    {
        if (visited[i] == false)
        {
            dfs(i);
            print();
            cout << endl;
            arr.clear();
        }

    }
    for (int i = 0; i < 1000; i++)
        visited[i] = false;
    for (int i = 0; i < n; i++)
    {
        if (visited[i] == false)
        {
            bfs(i);
            print();
            cout << endl;
            arr.clear();
        }

    }

}